home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / More Source / Libraries / VideoToolbox 95.04.18 / VideoToolboxSources / nrand.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-09  |  2.6 KB  |  71 lines  |  [TEXT/MMCC]
  1. /*
  2. nrand.c
  3. nrand(n) returns a random integer in the range [0, n-1], provided n>0. If n is zero
  4. the returned value is zero.
  5.  
  6. nrandU() and nrandUL() are obsolete; use nrand() instead.
  7.  
  8. NOTE:
  9. Frans Cornelissen showed me another way to implement nrand: rand()%n or
  10. randU()%n, instead of my n*rand()>>15 or n*randU()>>16. I used TimeCPU to
  11. compare the speeds; they're about the same:
  12.      22.362 µs    i=nrand(127);
  13.      19.684 µs    i=127L*randU()>>16;
  14.      18.226 µs    i=127L*rand()>>15;
  15.      20.891 µs    i=randU()%(unsigned short)127;
  16.      20.498 µs    i=rand()%127;
  17. This was on a PowerBook 170, compiled by CodeWarrior 5.5 using 4-byte ints.
  18. Note that the overhead of calling the nrand() subroutine (and its test of n),
  19. as opposed to evaluating the code inline, is only 3 µs out of 22 µs.
  20.  
  21. HISTORY:
  22. 4/29/88    dgp    wrote it.
  23. 3/19/90    dgp    made it portable between THINK C and MPW C.
  24. 9/13/92    dgp    Using THINK C's Disassembler I noticed that I could substantially speed
  25.             up the code, replacing the long division by a bit shift. The answers for 
  26.             legal values of n, i.e. n>0, are unchanged, but the answers for values of 
  27.             n outside that range have changed because I now explicitly cast n
  28.             to unsigned long rather than long. (Bit shifting and division give different
  29.             answers when the numerator is negative.)
  30.             Added nrandU() and nrandUL().
  31. 9/18/92    dgp    Cast rand() from int to unsigned short to prompt THINK C to generate 
  32.             tighter code.
  33. 3/26/94    dgp Replaced all three routines (nrand, nrandU, and nrandUL) by one universal
  34.             routine, nrand, that uses integer arithmetic (as in nrandU) if n is small 
  35.             enough, and otherwise uses double arithmetic (as in nrandUL). However,
  36.             even for small n, the new routine differs from the old nrandU() because
  37.             I replaced the call to rand() by a call to randU() because this
  38.             allows us to use integer arithmetic for values of n up to
  39.             USHRT_MAX instead of just SHRT_MAX.        
  40. */
  41. #include "VideoToolbox.h"
  42. #include <assert.h>
  43.  
  44. unsigned long nrand(unsigned long n)
  45. {
  46.     if(ULONG_MAX/USHRT_MAX/USHRT_MAX>=1 && n<=USHRT_MAX)return n*randU()>>16;
  47.     else return (unsigned long)((double)n*randUL()/(ULONG_MAX+1.0));
  48. }
  49.  
  50. #if 0    // Old version, before March, 1994.
  51.     int nrand(short n)
  52.     {
  53.         assert(RAND_MAX+1UL==1UL<<15);
  54.         return (unsigned long)n*rand()>>15;
  55.     }
  56.         
  57.     #if RAND_MAX > ULONG_MAX/USHRT_MAX
  58.         #error "nrandU() assumes that an unsigned long can hold the product of unsigned short & rand()."
  59.     #endif
  60.     
  61.     unsigned short nrandU(unsigned short n)
  62.     {
  63.         assert(RAND_MAX+1UL==1UL<<15);
  64.         return (unsigned long)n*(unsigned short)rand()>>15;
  65.     }
  66.  
  67.     unsigned long nrandUL(unsigned long n)
  68.     {
  69.         return (unsigned long)((double)n*randUL()/(ULONG_MAX+1.0)); 
  70.     }
  71. #endif